/**
 * 需求: 不依赖额外空间交换两个数
 * <hr>
 * 算法: 位运算-异或运算交换两个数
 * <br>
 * 时间复杂度: O(1)
 * <br>
 * 空间复杂度: O(0)
 * <p>
 * 知识点:
 * <br>
 * 1. 值传递形参不会影响实参      <br>
 * 2. 引用传递形参会影响实参      <br>
 * 3. x^0=x; x^x=0;           <br>
 * 4. 位运算遵守交换律和结合律    <br>
 */
class SwapWithoutSpace {
    public static void main(String[] args) {
        int x = 1;
        int y = 2;
        System.out.printf("x = %d, y = %d%n", x, y);

        x ^= y;
        y ^= x;
        x ^= y;
        System.out.printf("x = %d, y = %d%n%n", x, y);


        // Integer 虽然是引用类型, 但是其被 final 修饰
        Integer a = 1;
        Integer b = 2;
        System.out.printf("a = %d, b = %d%n", a, b);
        swap(a, b);
        System.out.printf("a = %d, b = %d%n%n", a, b);

        // 使用引用类型类型
        Reference reference = new Reference(1, 2);
        System.out.println(reference);
        swap(reference);
        System.out.println(reference);
    }

    /**
     * 位运算-异或运算交换两个数
     * <br>
     * 时间复杂度: O(1)
     * <br>
     * 空间复杂度: O(0)
     * <p>
     * 知识点:
     * <br>
     * 1. 值传递形参不会影响实参      <br>
     * 2. x^0=x; x^x=0;           <br>
     * 3. 位运算遵守交换律和结合律    <br>
     */
    public static void swap(int x, int y) {
        x = x ^ y;
        y = x ^ y; // 此时, x = x ^ y; 等价于 (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x, 即 y = x;
        x = x ^ y; // 此时, x = x ^ y, y = x, 等价于 (x ^ y) ^ x = (x ^ x) ^ y = 0 ^ y = y, 即 x = y;
    }

    /**
     * 位运算-异或运算交换两个数
     * <p>
     * 引用传递形参会影响实参
     * <p>
     * 时间复杂度: O(1)
     * <br>
     * 空间复杂度: O(0)
     */
    public static void swap(Reference reference) {
        reference.a = reference.a ^ reference.b;
        reference.b = reference.a ^ reference.b;
        reference.a = reference.a ^ reference.b;
    }

    static class Reference {
        private int a;
        private int b;

        @Override
        public String toString() {
            return "Reference{a = " + a + ", b = " + b + '}';
        }

        public Reference(Integer a, Integer b) {
            this.a = a;
            this.b = b;
        }
    }
}
